package pro.softzhang.algo.lc200;

import java.util.*;

public class LC210_CourseScheduleII {
    public static void main(String[] args) {

    }

    static class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            Map<Integer, List<Integer>> graph = new HashMap<>();
            for (int i = 0; i < numCourses; i++) {
                graph.put(i, new LinkedList<>());
            }

            int[] inDegrees = new int[numCourses];
            for (int[] prereq : prerequisites) {
                graph.get(prereq[1]).add(prereq[0]);
                inDegrees[prereq[0]]++;
            }

            Queue<Integer> q = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) {
                if(inDegrees[i] == 0) {
                    q.add(i);
                }
            }

            List<Integer> order = new LinkedList<>();
            while (!q.isEmpty()) {
                int course = q.remove();
                order.add(course);
                for (int next : graph.get(course)) {
                    inDegrees[next]--;
                    if(inDegrees[next] == 0) {
                        q.add(next);
                    }
                }
            }

            return order.size() == numCourses ? order.stream().mapToInt(i -> i).toArray() : new int[0];
        }
    }
}
